#pragma once

#include "visited_list_pool.h"
#include "hnswlib.h"

#include <algorithm>
#include <fstream>
#include <iostream>
#include <random>
#include <unordered_set> // don't use set, use unordered_set instead

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

template<typename T>
void writeBinaryPOD(std::ostream &out, const T &podRef) {
    out.write((char *) &podRef, sizeof(T));
}

template<typename T>
static void readBinaryPOD(std::istream &in, T &podRef) {
    in.read((char *) &podRef, sizeof(T));
}
//重要的数据结构

/*
 * data_level0_memory_:
 * 用于存放最底层图的数据, 对于每一个单元, 其格式为(分先后顺序):
 * inner product的图结构
 *      linklistint: 用于存放出度数量
 *      cos_maxM0_ * int: 用于存放邻居的id
 * cosine的图结构, 和inner product相同
 * 向量数据
 *      dimension * sizeof(float): 数据随着维度从左到右依次递增
 * labeltype, 代表这个item对外的label
 */

/*
 * linkLists_:
 * 用于存放上层图结构, 一个二维可变长数组
 * 第一维的数量为number of item, 每一个元素都是一个指针, 第i个指针指向第i个item的上层图情况
 * 第二维存放单个item上层图的邻居情况, 第i个单元代表第i层图的邻居信息, 每一个单元的格式为(根据先后顺序表示):
 *      linklistint: 用于存放出度数量
 *      cos_M_ * sizeof(int): cosine的上层图邻居, 对于多余的节点就存放在后面
 * 注意只有cosine有上层图, inner product没有
 */

/*
 * vector<int> elementLevels
 * 大小为number of item, 记录了每一个item有多少层
 * vector<float> elementNorms
 * 大小为number of item, 记录了每一个item的norm, 根据external_id进行排序而不是internal
 */

#define DEBUG_LIB 1
namespace hnswlib {
    typedef unsigned int tableint;
    typedef unsigned int linklistsizeint;

    template<typename dist_t>
    class HierarchicalNSW : public AlgorithmInterface<dist_t> {
    public:
        HierarchicalNSW(SpaceInterface <dist_t> *s) {

        }

        HierarchicalNSW(SpaceInterface <dist_t> *s, const string &location, bool nmslib = false) {
            LoadIndex(location, s);
        }

        HierarchicalNSW(SpaceInterface <dist_t> *s, size_t maxElements, size_t M, size_t cos_M, size_t efConstruction
                        , size_t cos_efConstruction) : ll_locks(maxElements), elementLevels(maxElements) {
            maxelements_ = maxElements;

            data_size_ = s->get_data_size();
            fstdistfunc_ = s->get_dist_func();
            dist_func_param_ = s->get_dist_func_param();
            M_ = M;
            maxM_ = M_;   // max_M_ is no longer needed as we don't have inner product graphs on upper layers
            maxM0_ = M_ * 2;
            efConstruction_ = efConstruction;
            ef_ = 7;      // ?????

            cos_M_ = cos_M;
            cos_maxM_ = cos_M_;
            cos_maxM0_ = cos_M_ * 2;
            cos_efConstruction_ = cos_efConstruction;
            cos_ef_ = 1;


            size_links_level0_ip_ = maxM0_ * sizeof(tableint) + sizeof(linklistsizeint);
            size_links_level0_cos_ = cos_maxM0_ * sizeof(tableint) + sizeof(linklistsizeint);
            size_links_level0_ = size_links_level0_ip_ + size_links_level0_cos_;
            size_data_per_element_ = size_links_level0_ + data_size_ + sizeof(labeltype);
            offsetData_ = size_links_level0_;
            label_offset_ = size_links_level0_ + data_size_;
            //cout << offsetData_ << "\t" << label_offset_ << "\n";
            //cout << size_links_level0_ << "\t" << data_size_ << "\t" << sizeof(labeltype) << "\n";

            data_level0_memory_ = (char *) malloc(maxelements_ * size_data_per_element_);

            size_t predicted_size_per_element = size_data_per_element_ + sizeof(void *) + 8 + 8 + 2 * 8;
            //cout << "size_mb=" << maxelements_*(predicted_size_per_element) / (1000 * 1000) << "\n";
            cur_element_count = 0;

            visitedlistpool = new VisitedListPool(1, maxElements);



            //initializations for special treatment of the first node
            enterpoint_node = -1;
            maxlevel_ = -1;

            linkLists_ = (char **) malloc(sizeof(void *) * maxelements_);
            size_links_per_element_ = cos_maxM_ * sizeof(tableint) + sizeof(linklistsizeint);
            mult_ = 1 / log(1.0 * M_);
            revSize_ = 1.0 / mult_;
        }

        ~HierarchicalNSW() {

            free(data_level0_memory_);
            for (tableint i = 0; i < cur_element_count; i++) {
                if (elementLevels[i] > 0)
                    free(linkLists_[i]);
            }
            free(linkLists_);
            delete visitedlistpool;
        }

        size_t maxelements_;
        size_t cur_element_count;
        size_t size_data_per_element_;
        size_t size_links_per_element_;

        size_t M_;
        size_t maxM_;
        size_t maxM0_;
        size_t efConstruction_;
        int delaunay_type_;
        double mult_, revSize_;
        int maxlevel_;

        size_t cos_M_, cos_maxM_, cos_maxM0_;
        size_t cos_efConstruction_;
        size_t cos_ef_;

        VisitedListPool *visitedlistpool;
        mutex cur_element_count_guard_;
        mutex MaxLevelGuard_;
        vector <mutex> ll_locks;
        tableint enterpoint_node;

        size_t dist_calc;
        size_t size_links_level0_;
        size_t offsetData_;

        size_t size_links_level0_ip_;
        size_t size_links_level0_cos_;

        char *data_level0_memory_;
        char **linkLists_;
        vector<int> elementLevels;
        vector<float> elementNorms;


        size_t data_size_;
        size_t label_offset_;
        DISTFUNC <dist_t> fstdistfunc_;
        void *dist_func_param_;
        std::default_random_engine generator = std::default_random_engine(100);

        inline labeltype getExternalLabel(tableint internal_id) {
            return *((labeltype * )(data_level0_memory_ + internal_id * size_data_per_element_ + label_offset_));
        }

        inline labeltype *getExternalLabeLp(tableint internal_id) {
            return (labeltype * )(data_level0_memory_ + internal_id * size_data_per_element_ + label_offset_);
        }

        inline char *getDataByInternalId(tableint internal_id) {
            return (data_level0_memory_ + internal_id * size_data_per_element_ + offsetData_);
        }

        int getRandomLevel(double revSize) {
            std::uniform_real_distribution<double> distribution(0.0, 1.0);
            double r = -log(distribution(generator)) * revSize;
            //cout << revSize;
            return (int) r;
        }

        //搜索当前层的元素并返回topk
        std::priority_queue<std::pair<dist_t, tableint  >> searchBaseLayer(tableint ep, void *datapoint, int layer) {
            //初始化visited list
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint  >> topResults;
            std::priority_queue<std::pair<dist_t, tableint >> candidateSet;
            dist_t dist = fstdistfunc_(datapoint, getDataByInternalId(ep), dist_func_param_) /
                          elementNorms[getExternalLabel(ep)];

            topResults.emplace(dist, ep);
            candidateSet.emplace(-dist, ep);
            massVisited[ep] = currentV;
            dist_t lowerBound = dist;

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;

                unique_lock <mutex> lock(ll_locks[curNodeNum]);

                int *data;// = (int *)(linkList0_ + curNodeNum * size_links_per_element0_);
                if (layer == 0)
                    data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_ + size_links_level0_ip_);
                else
                    data = (int *) (linkLists_[curNodeNum] + (layer - 1) * size_links_per_element_);
                int size = *data;
                tableint *datal = (tableint *) (data + 1);
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(getDataByInternalId(*datal), _MM_HINT_T0);
                _mm_prefetch(getDataByInternalId(*(datal + 1)), _MM_HINT_T0);

                for (int j = 0; j < size; j++) {
                    tableint tnum = *(datal + j);
                    _mm_prefetch((char *) (massVisited + *(datal + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(getDataByInternalId(*(datal + j + 1)), _MM_HINT_T0);
                    if (!(massVisited[tnum] == currentV)) {
                        massVisited[tnum] = currentV;
                        char *currObj1 = (getDataByInternalId(tnum));

                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_) /
                                      elementNorms[getExternalLabel(tnum)];
                        if (topResults.top().first > dist || topResults.size() < cos_efConstruction_) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(getDataByInternalId(candidateSet.top().second), _MM_HINT_T0);
                            topResults.emplace(dist, tnum);
                            if (topResults.size() > cos_efConstruction_) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }
            visitedlistpool->releaseVisitedList(vl);

            return topResults;
        }

        /*
        struct CompareByFirst {
          constexpr bool operator()(pair<dist_t, tableint> const & a,
            pair<dist_t, tableint> const & b) const noexcept
          {
            return a.first < b.first;
          }
        };
        */

        //和searchBaseLayer没有本质差别, 一个是ef_construction固定, 一个不固定
        std::priority_queue<std::pair<dist_t, tableint>> searchBaseLayerST(tableint ep, void *datapoint, size_t ef) {
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint>> topResults;
            std::priority_queue<std::pair<dist_t, tableint>> candidateSet;
            dist_t dist = fstdistfunc_(datapoint, getDataByInternalId(ep), dist_func_param_) /
                          elementNorms[getExternalLabel(ep)];
            dist_calc++;
            topResults.emplace(dist, ep);
            candidateSet.emplace(-dist, ep);
            massVisited[ep] = currentV;
            dist_t lowerBound = dist;

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;
                int *data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_ + size_links_level0_ip_);
                int size = *data;
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(data_level0_memory_ + (*(data + 1)) * size_data_per_element_ + offsetData_, _MM_HINT_T0);
                _mm_prefetch((char *) (data + 2), _MM_HINT_T0);

                for (int j = 1; j <= size; j++) {
                    int tnum = *(data + j);
                    _mm_prefetch((char *) (massVisited + *(data + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(data_level0_memory_ + (*(data + j + 1)) * size_data_per_element_ + offsetData_,
                                 _MM_HINT_T0);////////////
                    if (!(massVisited[tnum] == currentV)) {

                        massVisited[tnum] = currentV;

                        char *currObj1 = (getDataByInternalId(tnum));
                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_) /
                                      elementNorms[getExternalLabel(tnum)];
                        dist_calc++;
                        if (topResults.top().first > dist || topResults.size() < ef) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(data_level0_memory_ + candidateSet.top().second * size_data_per_element_ +
                                         size_links_level0_ip_,///////////
                                         _MM_HINT_T0);////////////////////////

                            topResults.emplace(dist, tnum);

                            if (topResults.size() > ef) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }

            visitedlistpool->releaseVisitedList(vl);
            return topResults;
        }

        /*
         * 在inner_product中输入cosine图得到的结果, 在最底层中在inner_product进行搜索
         * 将cosine图得到的结果的邻居作为enter point并在inner product图中进行搜索得到这一层的candidate
         */
        std::priority_queue<std::pair<dist_t, tableint>> searchBaseLayerST_inner_product(
                vector <pair<dist_t, tableint>> starting_points, void *datapoint, size_t ef) {
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint>> topResults; //小根堆, 距离函数为MIPS
            std::priority_queue<std::pair<dist_t, tableint>> precandidateSet; //大根堆, 一开始存放enter point, 用于得到candidateSet
            std::priority_queue<std::pair<dist_t, tableint>> candidateSet; //大根堆, 一开始存放enter point真正的邻居, 用于进行真正的beam search
            /*
             * 从enter point出发(由precandidateSet维护)迭代一次, 就是找到enter point的邻居并放到candidateSet中, 这个过程中还会将可能的结果放到topResults中
             * 对candiateSet出发而进行真正的beam search
             */

            for (auto &ele : starting_points) {
                topResults.emplace(ele.first, ele.second);
                precandidateSet.emplace(-ele.first, ele.second);
                //将所有的点设置为-1 (应该是都设置成已经访问过)
                massVisited[ele.second] = currentV;
            }

            // dist_t dist = fstdistfunc_(datapoint, getDataByInternalId(ep), dist_func_param_);
            // dist_calc++;
            dist_t lowerBound = topResults.top().first;

            while (!precandidateSet.empty()) {
                //precandidateSet就是进行beam search时需要迭代的点
                pair <dist_t, tableint> curr_el_pair = precandidateSet.top();
                precandidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;
                int *data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_);
                int size = *data;
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(data_level0_memory_ + (*(data + 1)) * size_data_per_element_ + offsetData_, _MM_HINT_T0);
                _mm_prefetch((char *) (data + 2), _MM_HINT_T0);

                //对当前迭代点的邻居进行搜索
                for (int j = 1; j <= size; j++) {
                    int tnum = *(data + j);
                    _mm_prefetch((char *) (massVisited + *(data + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(data_level0_memory_ + (*(data + j + 1)) * size_data_per_element_ + offsetData_,
                                 _MM_HINT_T0);////////////
                    //如果邻居在此之前没有被访问过
                    if (!(massVisited[tnum] == currentV)) {

                        massVisited[tnum] = currentV;

                        char *currObj1 = (getDataByInternalId(tnum));
                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_);
                        dist_calc++;
                        //如果candidate的数量小于ef或者大于topk的lower bound, 就将candidate插入进去
                        if (topResults.top().first > dist || topResults.size() < ef) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(
                                    data_level0_memory_ + candidateSet.top().second * size_data_per_element_,///////////
                                    _MM_HINT_T0);////////////////////////

                            topResults.emplace(dist, tnum);

                            if (topResults.size() > ef) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;
                int *data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_);
                int size = *data;
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(data_level0_memory_ + (*(data + 1)) * size_data_per_element_ + offsetData_, _MM_HINT_T0);
                _mm_prefetch((char *) (data + 2), _MM_HINT_T0);

                for (int j = 1; j <= size; j++) {
                    int tnum = *(data + j);
                    _mm_prefetch((char *) (massVisited + *(data + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(data_level0_memory_ + (*(data + j + 1)) * size_data_per_element_ + offsetData_,
                                 _MM_HINT_T0);////////////
                    if (!(massVisited[tnum] == currentV)) {

                        massVisited[tnum] = currentV;

                        char *currObj1 = (getDataByInternalId(tnum));
                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_);
                        dist_calc++;
                        if (topResults.top().first > dist || topResults.size() < ef) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(
                                    data_level0_memory_ + candidateSet.top().second * size_data_per_element_,///////////
                                    _MM_HINT_T0);////////////////////////

                            topResults.emplace(dist, tnum);

                            if (topResults.size() > ef) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }

            visitedlistpool->releaseVisitedList(vl);
            return topResults;
        }


        void getNeighborsByHeuristic2(tableint cur_c, std::priority_queue<std::pair<dist_t, tableint>> &topResults
                                      , const int NN) {
            if (topResults.size() < NN) {
                return;
            }
            std::priority_queue<std::pair<dist_t, tableint>> resultSet;
            std::priority_queue<std::pair<dist_t, tableint>> templist;
            vector <std::pair<dist_t, tableint>> returnlist;
            while (topResults.size() > 0) {
                resultSet.emplace(-topResults.top().first, topResults.top().second);
                topResults.pop();
            }

            while (resultSet.size()) {
                if (returnlist.size() >= NN)
                    break;
                std::pair<dist_t, tableint> curen = resultSet.top();
                dist_t dist_to_query = -curen.first / elementNorms[getExternalLabel(cur_c)];
                resultSet.pop();
                bool good = true;
                for (std::pair<dist_t, tableint> curen2 : returnlist) {
                    dist_t curdist =
                            fstdistfunc_(getDataByInternalId(curen2.second), getDataByInternalId(curen.second),
                                         dist_func_param_)
                            / elementNorms[getExternalLabel(curen2.second)] /
                            elementNorms[getExternalLabel(curen.second)];
                    // coeff * curdist < dist_to_query, we can adjust the coefficient here to get different performance
                    if (curdist < dist_to_query) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    returnlist.push_back(curen);
                }
            }

            for (std::pair<dist_t, tableint> curen2 : returnlist) {

                topResults.emplace(-curen2.first, curen2.second);
            }
        }

        linklistsizeint *get_linklist0(tableint cur_c) {
            return (linklistsizeint *) (data_level0_memory_ + cur_c * size_data_per_element_);
        };

        linklistsizeint *get_linklist(tableint cur_c, int level) {
            return (linklistsizeint *) (linkLists_[cur_c] + (level - 1) * size_links_per_element_);
        };

        /*
         * 根据candidate对要插入的点筛选出neighbor
         * 连接要插入的点及其邻居 (双向)
         * 如果邻居的度超过了threshold, 就将其邻居和要插入的边一起当成candidate做筛选, 从而更新neighbor
         */
        void mutuallyConnectNewElement(void *datapoint, tableint cur_c
                                       , std::priority_queue<std::pair<dist_t, tableint  >> topResults, int level) {

            size_t Mcurmax = level ? cos_maxM_ : cos_maxM0_;
            getNeighborsByHeuristic2(cur_c, topResults, cos_M_);
            //topResults是cosine的小根堆
            while (topResults.size() > cos_M_) {
                throw exception();
                topResults.pop();
            }
            //rez存的是topk的id, 从左到右distance依次增加, 越来越不相似
            vector <tableint> rez;
            rez.reserve(cos_M_);
            while (topResults.size() > 0) {
                rez.push_back(topResults.top().second);
                topResults.pop();
            }
            {
                linklistsizeint *ll_cur;
                if (level == 0)
                    ll_cur = (linklistsizeint *) (data_level0_memory_ + cur_c * size_data_per_element_ +
                                                  size_links_level0_ip_);
                else
                    ll_cur = (linklistsizeint *) (linkLists_[cur_c] + (level - 1) * size_links_per_element_);
                //插入的时候由于所有的数据都设置为0, 那么对于将要插入的元素, 其位置就必然不可能为0, 如果为0, 就要么程序有bug, 要么之前已经有数据插入了
                if (*ll_cur) {
                    cout << *ll_cur << "\n";
                    cout << elementLevels[cur_c] << "\n";
                    cout << level << "\n";
                    throw runtime_error("Should be blank");
                }
                *ll_cur = rez.size();
                tableint *data = (tableint *) (ll_cur + 1);

                //将通过heuristic得到的结果插入到数据结构中
                for (int idx = 0; idx < rez.size(); idx++) {
                    if (data[idx])
                        throw runtime_error("Should be blank");
                    if (level > elementLevels[rez[idx]])
                        throw runtime_error("Bad level");

                    data[idx] = rez[idx];
                }
            }
            // 连接邻居与将要插入的节点, 如果邻居的度超过了M就剪枝
            for (int idx = 0; idx < rez.size(); idx++) {

                unique_lock <mutex> lock(ll_locks[rez[idx]]);

                if (rez[idx] == cur_c)
                    throw runtime_error("Connection to the same element");
                linklistsizeint *ll_other;
                if (level == 0)
                    ll_other = (linklistsizeint *) (data_level0_memory_ + rez[idx] * size_data_per_element_ +
                                                    size_links_level0_ip_);
                else
                    ll_other = (linklistsizeint *) (linkLists_[rez[idx]] + (level - 1) * size_links_per_element_);
                if (level > elementLevels[rez[idx]])
                    throw runtime_error("Bad level");
                int sz_link_list_other = *ll_other;

                if (sz_link_list_other > Mcurmax || sz_link_list_other < 0)
                    throw runtime_error("Bad sz_link_list_other");

                if (sz_link_list_other < Mcurmax) {
                    //邻居的出度小于M
                    tableint *data = (tableint *) (ll_other + 1);
                    data[sz_link_list_other] = cur_c;
                    *ll_other = sz_link_list_other + 1;
                } else {
                    // finding the "weakest" element to replace it with the new one
                    tableint *data = (tableint *) (ll_other + 1);
                    //将当前迭代的邻居和邻居的邻居插入到优先队列中
                    dist_t d_max =
                            fstdistfunc_(getDataByInternalId(cur_c), getDataByInternalId(rez[idx]), dist_func_param_)
                            / elementNorms[getExternalLabel(cur_c)];
                    // Heuristic:
                    std::priority_queue<std::pair<dist_t, tableint>> candidates;
                    candidates.emplace(d_max, cur_c);

                    for (int j = 0; j < sz_link_list_other; j++) {
                        candidates.emplace(fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]),
                                                        dist_func_param_) / elementNorms[getExternalLabel(data[j])],
                                           data[j]);
                    }
                    //对优先队列进行剪枝
                    getNeighborsByHeuristic2(rez[idx], candidates, Mcurmax);
                    //将剪枝后的结果赋值给邻居的临近表
                    int indx = 0;
                    while (candidates.size() > 0) {
                        data[indx] = candidates.top().second;
                        candidates.pop();
                        indx++;
                    }
                    *ll_other = indx;
                    // Nearest K:
                    /*int indx = -1;
                    for (int j = 0; j < sz_link_list_other; j++) {
                        dist_t d = fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]), dist_func_param_);
                        if (d > d_max) {
                            indx = j;
                            d_max = d;
                        }
                    }
                    if (indx >= 0) {
                        data[indx] = cur_c;
                    } */
                }

            }
        }

        /*
         * 和mutuallyConnectNewElement唯一不同的地方在于, 这里对邻居边没有使用heuristic进行剪枝, 但是cosine距离就有
         */
        void mips_mutuallyConnectNewElement(void *datapoint, tableint cur_c
                                            , std::priority_queue<std::pair<dist_t, tableint  >> topResults) {

            size_t Mcurmax = maxM0_;
            while (topResults.size() > maxM_) {
                topResults.pop();
            }
            vector <tableint> rez;
            rez.reserve(maxM_);
            while (topResults.size() > 0) {
                rez.push_back(topResults.top().second);
                topResults.pop();
            }
            {
                linklistsizeint *ll_cur;
                ll_cur = (linklistsizeint *) (data_level0_memory_ + cur_c * size_data_per_element_);
                if (*ll_cur) {
                    cout << *ll_cur << "\n";
                    throw runtime_error("Should be blank");
                }
                *ll_cur = rez.size();
                tableint *data = (tableint *) (ll_cur + 1);

                for (int idx = 0; idx < rez.size(); idx++) {
                    if (data[idx])
                        throw runtime_error("Should be blank");

                    data[idx] = rez[idx];
                }
            }
            for (int idx = 0; idx < rez.size(); idx++) {

                // ?????????????????? 20190515
                unique_lock <mutex> lock(ll_locks[rez[idx]]);

                if (rez[idx] == cur_c)
                    throw runtime_error("Connection to the same element");
                linklistsizeint *ll_other;
                ll_other = (linklistsizeint *) (data_level0_memory_ + rez[idx] * size_data_per_element_);
                int sz_link_list_other = *ll_other;

                if (sz_link_list_other > Mcurmax || sz_link_list_other < 0)
                    throw runtime_error("Bad sz_link_list_other");

                if (sz_link_list_other < Mcurmax) {
                    tableint *data = (tableint *) (ll_other + 1);
                    data[sz_link_list_other] = cur_c;
                    *ll_other = sz_link_list_other + 1;
                } else {
                    // finding the "weakest" element to replace it with the new one
                    tableint *data = (tableint *) (ll_other + 1);
                    dist_t d_max = fstdistfunc_(getDataByInternalId(cur_c), getDataByInternalId(rez[idx]),
                                                dist_func_param_);
                    // Heuristic:
                    std::priority_queue<std::pair<dist_t, tableint>> candidates;
                    candidates.emplace(d_max, cur_c);

                    for (int j = 0; j < sz_link_list_other; j++) {
                        candidates.emplace(fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]),
                                                        dist_func_param_), data[j]);
                    }

                    // getNeighborsByHeuristic2(rez[idx], candidates, Mcurmax);
                    while (candidates.size() > Mcurmax) {
                        candidates.pop();
                    }

                    int indx = 0;
                    while (candidates.size() > 0) {
                        data[indx] = candidates.top().second;
                        candidates.pop();
                        indx++;
                    }
                    *ll_other = indx;
                    // Nearest K:
                    /*int indx = -1;
                    for (int j = 0; j < sz_link_list_other; j++) {
                        dist_t d = fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]), dist_func_param_);
                        if (d > d_max) {
                            indx = j;
                            d_max = d;
                        }
                    }
                    if (indx >= 0) {
                        data[indx] = cur_c;
                    } */
                }
            }
        }

        mutex global;
        size_t ef_;

        void setEf(size_t ef) {
            ef_ = ef;
        }

        void setCosEf(size_t cos_ef) {
            cos_ef_ = cos_ef;
        }

        //插入点
        void addPoint(void *datapoint, labeltype label, int level = -1) {

            tableint cur_c = 0;
            {
                unique_lock <mutex> lock(cur_element_count_guard_);
                if (cur_element_count >= maxelements_) {
                    cout << "The number of elements exceeds the specified limit\n";
                    throw runtime_error("The number of elements exceeds the specified limit");
                };
                cur_c = cur_element_count;
                cur_element_count++;
                if (cur_element_count % 100000 == 0) cout << "count : " << cur_element_count << endl;
            }
            unique_lock <mutex> lock_el(ll_locks[cur_c]);
            int curlevel = getRandomLevel(mult_);
            if (level > 0)
                curlevel = level;
            elementLevels[cur_c] = curlevel;


            unique_lock <mutex> templock(global);
            int maxlevelcopy = maxlevel_;
            if (curlevel <= maxlevelcopy)
                templock.unlock();
            tableint currObj = enterpoint_node;


            memset(data_level0_memory_ + cur_c * size_data_per_element_, 0, size_data_per_element_);
            // Initialisation of the data and label
            memcpy(getExternalLabeLp(cur_c), &label, sizeof(labeltype));
            memcpy(getDataByInternalId(cur_c), datapoint, data_size_);


            if (curlevel) {
                linkLists_[cur_c] = (char *) malloc(size_links_per_element_ * curlevel);
                memset(linkLists_[cur_c], 0, size_links_per_element_ * curlevel);
            }
            if (currObj != -1) {

                //当将要插入的item的level比maxlevel小, 就从maxlevel到curlevel通过greedy search检索出距离将要插入的item最近的item, 此时采用的是cosine similarity
                if (curlevel < maxlevelcopy) {

                    // 20190515 I am not sure if it should be divided by a single norm(id) or both norms (getting actual cosine value)
                    // 计算插入元素和enter_point的距离 (inner product) 除以将要插入元素的norm, 就是cosine距离
                    // getDataByInternalId(currObj): enter_point, datapoint: 将要插入的数据点
                    dist_t curdist = fstdistfunc_(datapoint, getDataByInternalId(currObj), dist_func_param_) /
                                     elementNorms[getExternalLabel(currObj)];
                    //当插入节点的层数小于最高层数, 就在上层进行ef_search=1的greedy search, 该过程改变的变量为curObj
                    for (int level = maxlevelcopy; level > curlevel; level--) {
                        bool changed = true;
                        while (changed) {
                            changed = false;
                            int *data;
                            unique_lock <mutex> lock(ll_locks[currObj]);
                            data = (int *) (linkLists_[currObj] + (level - 1) * size_links_per_element_);
                            int size = *data;
                            tableint *datal = (tableint *) (data + 1);
                            //对currObj在level层中的邻居进行遍历, 就是进行greedy search, ef_search = 1
                            for (int i = 0; i < size; i++) {
                                tableint cand = datal[i];
                                if (cand < 0 || cand > maxelements_)
                                    throw runtime_error("cand error");
                                dist_t d = fstdistfunc_(datapoint, getDataByInternalId(cand), dist_func_param_) /
                                           elementNorms[getExternalLabel(cand)];
                                if (d < curdist) {
                                    curdist = d;
                                    currObj = cand;
                                    changed = true;
                                }
                            }
                        }
                    }
                }

                for (int level = min(curlevel, maxlevelcopy); level >= 0; level--) {
                    if (level > maxlevelcopy || level < 0)
                        throw runtime_error("Level error");

                    // currObj may be changed during the iteration; worth a trial
                    std::priority_queue<std::pair<dist_t, tableint  >> topResults = searchBaseLayer(currObj, datapoint,
                                                                                                    level);
                    mutuallyConnectNewElement(datapoint, cur_c, topResults, level);

                    if (level == 0) {
                        //inner_product图的建图方式为将cosine的结果放在inner_product的图中搜索, 并将搜索的结果连接到新的点中
                        // put elements in topResults and their neighbors (even neighbors of mips neighbors) into MIPS queue
                        //cos_res为cosine距离下的candidate, 从左到右cosine距离依次增大, 其显式的距离都转换成了inner product
                        vector <pair<dist_t, tableint>> cos_res;
                        cos_res.reserve(cos_M_);
                        while (topResults.size() > 0) {
                            tableint tmp_id = topResults.top().second;
                            dist_t tmp_ip = topResults.top().first * elementNorms[getExternalLabel(tmp_id)];
                            cos_res.push_back(make_pair(tmp_ip, tmp_id));
                            topResults.pop();
                        }
                        std::priority_queue<std::pair<dist_t, tableint>> mips_topResults = searchBaseLayerST_inner_product(
                                cos_res, datapoint, efConstruction_);
                        // I don't need heuristic for mips inside the following function
                        mips_mutuallyConnectNewElement(datapoint, cur_c, mips_topResults);
                    }
                }
            } else {
                //插入第一个元素需要执行的语句
                // Do nothing for the first element
                enterpoint_node = 0;
                maxlevel_ = curlevel;

            }

            //Releasing lock for the maximum level
            if (curlevel > maxlevelcopy) {
                enterpoint_node = cur_c;
                maxlevel_ = curlevel;
            }
        };

        //先经过一个cosine graph, 然后经过一个inner product graph
        std::priority_queue<std::pair<dist_t, labeltype >> searchKnn(void *query_data, int k) {
            tableint currObj = enterpoint_node;
            dist_t curdist = fstdistfunc_(query_data, getDataByInternalId(enterpoint_node), dist_func_param_) /
                             elementNorms[getExternalLabel(enterpoint_node)];
            dist_calc++;
            // hnsw的上层图搜索, 至今进行greedy walk
            for (int level = maxlevel_; level > 0; level--) {
                bool changed = true;
                while (changed) {
                    changed = false;
                    int *data;
                    data = (int *) (linkLists_[currObj] + (level - 1) * size_links_per_element_);
                    int size = *data;
                    tableint *datal = (tableint *) (data + 1);
                    for (int i = 0; i < size; i++) {
                        tableint cand = datal[i];
                        if (cand < 0 || cand > maxelements_)
                            throw runtime_error("cand error");
                        dist_t d = fstdistfunc_(query_data, getDataByInternalId(cand), dist_func_param_) /
                                   elementNorms[getExternalLabel(cand)];
                        dist_calc++;
                        if (d < curdist) {
                            curdist = d;
                            currObj = cand;
                            changed = true;
                        }
                    }
                }
            }


            // here I set cos_ef_ to cos_M_
            // zzzzz
            std::priority_queue<std::pair<dist_t, tableint>> topResults = searchBaseLayerST(currObj, query_data,
                                                                                            cos_ef_);

            vector <pair<dist_t, tableint>> cos_res;
            // cos_res.reserve(cos_M_);
            while (topResults.size() > 0) {
                tableint tmp_id = topResults.top().second;
                dist_t tmp_ip = topResults.top().first * elementNorms[getExternalLabel(tmp_id)];
                cos_res.push_back(make_pair(tmp_ip, tmp_id));
                topResults.pop();
            }
            std::priority_queue<std::pair<dist_t, tableint>> mips_topResults = searchBaseLayerST_inner_product(cos_res,
                                                                                                               query_data,
                                                                                                               ef_);


            std::priority_queue<std::pair<dist_t, labeltype >> results;
            while (mips_topResults.size() > k) {
                mips_topResults.pop();
            }
            while (mips_topResults.size() > 0) {
                std::pair<dist_t, tableint> rez = mips_topResults.top();
                results.push(std::pair<dist_t, labeltype>(rez.first, getExternalLabel(rez.second)));
                mips_topResults.pop();
            }
            return results;
        };

        std::priority_queue<std::pair<dist_t, tableint>> searchKnnInternal(void *query_data, int k) {
            tableint currObj = enterpoint_node;
            dist_t curdist = fstdistfunc_(query_data, getDataByInternalId(enterpoint_node), dist_func_param_);
            dist_calc++;
            for (int level = maxlevel_; level > 0; level--) {
                bool changed = true;
                while (changed) {
                    changed = false;
                    int *data;
                    data = (int *) (linkLists_[currObj] + (level - 1) * size_links_per_element_);
                    int size = *data;
                    tableint *datal = (tableint *) (data + 1);
                    for (int i = 0; i < size; i++) {
                        tableint cand = datal[i];
                        if (cand < 0 || cand > maxelements_)
                            throw runtime_error("cand error");
                        dist_t d = fstdistfunc_(query_data, getDataByInternalId(cand), dist_func_param_);
                        dist_calc++;
                        if (d < curdist) {
                            curdist = d;
                            currObj = cand;
                            changed = true;
                        }
                    }
                }
            }

            //std::priority_queue< std::pair< dist_t, tableint  >> topResults = searchBaseLayer(currObj, query_data, 0);
            std::priority_queue<std::pair<dist_t, tableint  >> topResults = searchBaseLayerST(currObj, query_data, ef_);
            while (topResults.size() > k) {
                topResults.pop();
            }
            return topResults;
        };

        void SaveIndex(const string &location) {

            cout << "Saving index to " << location.c_str() << "\n";
            std::ofstream output(location, std::ios::binary);
            streampos position;

            writeBinaryPOD(output, maxelements_);
            writeBinaryPOD(output, cur_element_count);
            writeBinaryPOD(output, size_data_per_element_);
            writeBinaryPOD(output, label_offset_);
            writeBinaryPOD(output, offsetData_);
            writeBinaryPOD(output, maxlevel_);
            writeBinaryPOD(output, enterpoint_node);
            writeBinaryPOD(output, maxM_);

            writeBinaryPOD(output, maxM0_);
            writeBinaryPOD(output, M_);
            writeBinaryPOD(output, mult_);
            writeBinaryPOD(output, efConstruction_);


            writeBinaryPOD(output, cos_M_);
            writeBinaryPOD(output, cos_efConstruction_);
            for (size_t i = 0; i < maxelements_; ++i) {
                writeBinaryPOD(output, elementNorms[i]);
            }

            output.write(data_level0_memory_, maxelements_ * size_data_per_element_);

            for (size_t i = 0; i < maxelements_; i++) {
                unsigned int linkListSize = elementLevels[i] > 0 ? size_links_per_element_ * elementLevels[i] : 0;
                writeBinaryPOD(output, linkListSize);
                if (linkListSize)
                    output.write(linkLists_[i], linkListSize);
            }
            output.close();
        }

        void LoadIndex(const string &location, SpaceInterface <dist_t> *s) {


            //cout << "Loading index from " << location;
            std::ifstream input(location, std::ios::binary);
            streampos position;

            readBinaryPOD(input, maxelements_);
            readBinaryPOD(input, cur_element_count);
            readBinaryPOD(input, size_data_per_element_);
            readBinaryPOD(input, label_offset_);
            readBinaryPOD(input, offsetData_);
            readBinaryPOD(input, maxlevel_);
            readBinaryPOD(input, enterpoint_node);

            readBinaryPOD(input, maxM_);
            readBinaryPOD(input, maxM0_);
            readBinaryPOD(input, M_);
            readBinaryPOD(input, mult_);
            readBinaryPOD(input, efConstruction_);
            cout << efConstruction_ << "\n";

            readBinaryPOD(input, cos_M_);
            readBinaryPOD(input, cos_efConstruction_);
            for (size_t i = 0; i < maxelements_; ++i) {
                float temp;
                readBinaryPOD(input, temp);
                elementNorms.push_back(temp);
            }


            data_size_ = s->get_data_size();
            fstdistfunc_ = s->get_dist_func();
            dist_func_param_ = s->get_dist_func_param();

            data_level0_memory_ = (char *) malloc(maxelements_ * size_data_per_element_);
            input.read(data_level0_memory_, maxelements_ * size_data_per_element_);


            cos_maxM_ = cos_M_;
            cos_maxM0_ = 2 * cos_M_;
            size_links_level0_ip_ = maxM0_ * sizeof(tableint) + sizeof(linklistsizeint);
            size_links_level0_cos_ = cos_maxM0_ * sizeof(tableint) + sizeof(linklistsizeint);
            size_links_level0_ = offsetData_;

            size_links_per_element_ = cos_maxM_ * sizeof(tableint) + sizeof(linklistsizeint);

            visitedlistpool = new VisitedListPool(1, maxelements_);


            linkLists_ = (char **) malloc(sizeof(void *) * maxelements_);
            cout << maxelements_ << "\n";
            elementLevels = vector<int>(maxelements_);
            revSize_ = 1.0 / mult_;
            ef_ = 10;
            for (size_t i = 0; i < maxelements_; i++) {
                unsigned int linkListSize;
                readBinaryPOD(input, linkListSize);
                if (linkListSize == 0) {
                    elementLevels[i] = 0;

                    linkLists_[i] = nullptr;
                } else {
                    elementLevels[i] = linkListSize / size_links_per_element_;
                    linkLists_[i] = (char *) malloc(linkListSize);
                    input.read(linkLists_[i], linkListSize);
                }
            }


            input.close();
            size_t predicted_size_per_element = size_data_per_element_ + sizeof(void *) + 8 + 8 + 2 * 8;
            cout << "Loaded index, predicted size=" << maxelements_ * (predicted_size_per_element) / (1000 * 1000)
                 << "\n";
            return;
        }
    };

}
